#include <iostream>
#include "../head/TreeNode.h"

using namespace std;


// 112: Path Sum
// 时间复杂度: O(n), n为树的节点个数
// 空间复杂度: O(h), h为树的高度
class Solution {
public:
	bool hasPathSum(TreeNode* root, int sum) {
		if(root == NULL) return false;
		
		// 叶子结点 ，不再递归调用
		if(root->left == NULL && root->right == NULL)
			return sum == root->val;
		return hasPathSum(root->left, sum - root->val)
			|| hasPathSum(root->right, sum - root->val);
    }
};
